import pickle
import time
import sys
class LRStavka:
    def __init__(self, lr_stavka):

        self.desna_strana = []
        self.lijeva_strana = [lr_stavka[0]]
        self.desna_strana.extend(lr_stavka[1:])

        indeks = lr_stavka.index('*')

        self.ispred_tocke = lr_stavka[1:indeks]

        self.iza_tocke = lr_stavka[indeks+1:]

        self.lista_zapocinje = "TBD"


class Generator:
    def __init__(self):
        self.nezavrsni_znakovi=[]
        self.zavrsni_znakovi=[]
        self.znakovi=[]
        self.sinkronizacijski_znakovi=[]
        self.produkcije={}
        self.red_produkcija=[]
        self.pocetni=""
        self.prazni_znakovi=set([])
        self.tablica=set()
        self.lr_stavke=dict()


    def citaj(self):
        sys.stdin=open("./probni/minusLang.san","r")

        temp=sys.stdin.readline()
        temp=temp.split()
        self.nezavrsni_znakovi=temp[1:]
        self.pocetni=self.nezavrsni_znakovi[0]
        temp=sys.stdin.readline()
        temp=temp.split()
        self.zavrsni_znakovi=temp[1:]
        self.znakovi.extend(self.zavrsni_znakovi)
        self.znakovi.extend(self.nezavrsni_znakovi)

        temp=sys.stdin.readline()
        temp=temp.split()
        self.sinkronizacijski_znakovi=temp[1:]


        for line in sys.stdin:
            if len(line)==0:
                continue
            if line[0]=="<":
                zadnji=line.strip()

            else:
                if zadnji in self.produkcije:
                    self.produkcije[zadnji].append(line.strip())
                    self.red_produkcija.append(zadnji +"->"+ line.strip())

                else:
                    self.produkcije[zadnji]=[line.strip()]
                    self.red_produkcija.append(zadnji +"-"+ line.strip())


    def dodaj_pocetni(self):
        pocetni="<PNZ>"
        i=0
        while pocetni in self.produkcije:
            pocetni="<"+"PNZ"+i*"_"+">"
            i=i+1
        self.produkcije[pocetni]=[self.pocetni]
        self.pocetni=pocetni


    def izracunaj_prazne(self):
        temp_prazni_znakovi=set([])
        prvi=1
        while(self.prazni_znakovi != temp_prazni_znakovi or prvi==1):
            prvi=0
            self.prazni_znakovi=temp_prazni_znakovi.copy()
            for i in self.produkcije:
                for j in self.produkcije[i]:
                    znakovi_produkcije=j.split()
                    if znakovi_produkcije[0]=="$":
                        temp_prazni_znakovi.add(i)
                    else:
                        svi_prazni=1
                        for znak in znakovi_produkcije:
                            if znak not in temp_prazni_znakovi:
                                svi_prazni=0

                        if svi_prazni==1:
                            temp_prazni_znakovi.add(i)


    def zapocinje_izravno_znakom(self):
        for i in self.nezavrsni_znakovi:
            if i not in self.produkcije.keys():
                continue
            for j in self.znakovi:
                for k in self.produkcije[i]:
                    znakovi = k.split()
                    for l in znakovi:
                        if l == j:
                            self.tablica.add((i, j))
                        if l not in self.prazni_znakovi:
                            break


    def zapocinje_znakom(self):
        tablica2 = self.tablica.copy()
        ulazak = 1
        while self.tablica != tablica2 or ulazak:
            ulazak = 0
            self.tablica = tablica2.copy()
            for i in self.tablica:
                for j in self.tablica:
                    if i[1] != j[0]:
                        continue

                    for k in self.tablica:
                        if k[0]==j[0]:
                            tablica2.add((i[0], k[1]))



    def dodaj_tocke(self):
        for i in self.produkcije.items():
            self.lr_stavke[i[0]] = []
            for j in i[1]:
                znakovi = j.split()
                if znakovi == ['$']:
                    tmp = ['*']
                    self.lr_stavke[i[0]].append(tmp)
                else:
                    for k in range(0, len(znakovi)+1):
                        tmp = list(znakovi)
                        tmp.insert(k, '*')
                        self.lr_stavke[i[0]].append(tmp)


    def vrati_lr_stavke(self):
        stavke = []
        for i in self.lr_stavke.items():
            for j in i[1]:
                stavke.append(LRStavka([i[0]]+j))
        return stavke


#u LR-stavkama tocka se oznacava sa *, a kraj niza sa "#"

class e_NKA:

    sva_stanja = []         #tu su sva stanja koja su do sad napravljena
    LR_stavke = []
    ulazni_znakovi = []
    nezavrsni_znakovi = []
    tablica=set()
    pocetni_nezavrsni = ""
    prazni_znakovi = []

    prijelazi = dict()

    def __init__(self, stavke, zavrsni, nezavrsni, poc_nezavrs, prazni, tab):

        self.LR_stavke = stavke
        self.ulazni_znakovi = zavrsni + nezavrsni
        self.nezavrsni_znakovi = nezavrsni
        self.tablica = tab
        self.pocetni_nezavrsni = poc_nezavrs
        self.prazni_znakovi = prazni

    def zapocinje(self, niz):
        lista_zapocinje = []
        
        for i in niz:

            if (i[0] != "<"):
                lista_zapocinje.append(i)
                break

            for j in self.tablica:
                if (j[0] == i and j[1][0] != "<"):
                    lista_zapocinje.append(j[1])

            if (i not in self.prazni_znakovi):
                break
        return lista_zapocinje

    def dodaj_e_prijelaz(self, iz_stanja): #ovi parametri su svi od onog stanja iz kojeg se radi prijelaz

        nova_st = []
        nezavrsni_znak = iz_stanja.nakon_tocke
        nezavrsni_znak1 = []
        nezavrsni_znak1.append(nezavrsni_znak[0])
        beta = iz_stanja.nakon_tocke[1:]
        #for i in self.LR_stavke:
            #print(i.ispred_tocke, i.desna_strana)
        #print("____________")
        for i in self.LR_stavke:
            if (i.lijeva_strana[0] == nezavrsni_znak[0] and len(i.ispred_tocke) == 0): #pronadena je produkcija
                    #lijeva_strana je string, ostalo su liste stringova

                nova_lista = self.zapocinje(beta)
                generira_prazni_niz = 1
                for j in beta:                  #provjerava da li beta generira prazni niz

                    if (len(j) > 0):

                        if (j[0] == "<"):       #znaci da je nezavrsni znak
                            if (j in self.prazni_znakovi):
                                continue
                            else:
                                generira_prazni_niz = 0
                                break
                        else:                   #znaci da je zavrsni znak
                            generira_prazni_niz = 0
                            break
                    else:
                        break

                if (generira_prazni_niz == 1):

                    for j in iz_stanja.lista:           #radi uniju novostvorene i naslijedene liste
                        if (j not in nova_lista):
                            nova_lista.append(j)
                #print(nezavrsni_znak)
                tmp_stanje = Stanje(nezavrsni_znak1, [], i.iza_tocke, nova_lista) #prije tocke nije nista pa stavlja prazan niz

                if ( iz_stanja.naziv_stanja in self.prijelazi.keys() ):                     #stvori prijelaz u sva nova stanja
                    if ( "$" in self.prijelazi[iz_stanja.naziv_stanja].keys() ):
                        self.prijelazi[iz_stanja.naziv_stanja]["$"].append(tmp_stanje.naziv_stanja)
                    else:
                        self.prijelazi[iz_stanja.naziv_stanja]["$"] = [tmp_stanje.naziv_stanja]
                else:
                    self.prijelazi[iz_stanja.naziv_stanja]["$"] = [tmp_stanje.naziv_stanja]

                nova_st.append(tmp_stanje)
                
        return nova_st

    def dodaj_prijelaz_za_znak(self, iz_stanja):

        tmp_lista = []
        tmp_lista.append(iz_stanja.nakon_tocke[0])
        tmp_stanje = Stanje(iz_stanja.lijeva_strana, iz_stanja.prije_tocke + tmp_lista, iz_stanja.nakon_tocke[1:], iz_stanja.lista)
        znak_prijelaza = iz_stanja.nakon_tocke[0]

        if ( iz_stanja.naziv_stanja in self.prijelazi.keys() ):                     #stvori prijelaz u novo stanje
            if ( znak_prijelaza in self.prijelazi[iz_stanja.naziv_stanja].keys() ):
                self.prijelazi[iz_stanja.naziv_stanja][znak_prijelaza].append(tmp_stanje.naziv_stanja)
            else:
                self.prijelazi[iz_stanja.naziv_stanja][znak_prijelaza] = [tmp_stanje.naziv_stanja]
        else:
            self.prijelazi[iz_stanja.naziv_stanja] = {}
            self.prijelazi[iz_stanja.naziv_stanja][znak_prijelaza] = [tmp_stanje.naziv_stanja]

        return tmp_stanje

    def stvori_automat(self,pocetni):

        nova_stanja = []        #tu su stanja koja jos nisu obradena tj koja nemaju generirane prijelaze
        tmp_pocetno = Stanje([pocetni], [], [], [])
        tmp_pocetno.naziv_stanja = pocetni
        self.sva_stanja.append(tmp_pocetno)

        #prijelazi su u obliku dict{stanje: dict{znak: list(stanje)} }
        for i in self.LR_stavke:
            #print(i.desna_strana)                        #tu se ustanovi koje su pocetne produkcije i rade se nova stanja za njih
            if (i.lijeva_strana[0] == self.pocetni_nezavrsni and len (i.ispred_tocke) == 0):

                tmp_stanje = Stanje(i.lijeva_strana, i.ispred_tocke, i.iza_tocke, "#")

                if ( pocetni in self.prijelazi.keys() ):                     #stvori prijelaz u sva nova stanja
                    if ( "$" in self.prijelazi[pocetni].keys() ):
                        self.prijelazi[pocetni]["$"].append(tmp_stanje.naziv_stanja)
                    else:
                        self.prijelazi[pocetni]["$"] = [tmp_stanje.naziv_stanja]
                else:
                    self.prijelazi[pocetni] = {}
                    self.prijelazi[pocetni]["$"] = [tmp_stanje.naziv_stanja]

                postoji = 0
                for k in nova_stanja:
                    if ( tmp_stanje.naziv_stanja == k.naziv_stanja ):
                        postoji = 1

                if (postoji == 0):
                    nova_stanja.append(tmp_stanje)

        while ( len(nova_stanja) > 0 ):
            #print(len(nova_stanja))
            stanje = nova_stanja.pop()          #stanje se brise iz liste
            self.sva_stanja.append(stanje)      #tu se ubacuje u stanja koja su obradena tj za koja su generirani prijelazi

            if ( len(stanje.nakon_tocke) > 0 ):
                nova_stanja.append(self.dodaj_prijelaz_za_znak(stanje) )

                if ( stanje.nakon_tocke[0][0] == "<"):        #znaci da je nezavrsni znak
                    nova_stanja += self.dodaj_e_prijelaz(stanje)    #vraca nova stanja koje stvori

            stanja_za_izbacit = []
            #print(type(self.sva_stanja), type(nova_stanja), type(stanja_za_izbacit))
            for k in nova_stanja:                   #ovo se provjerava jer dva razlicita stanja mogu imati prijelaz u isto stanja pa tako mogu i stvoriti isto stanje
                for j in self.sva_stanja:
                    if (j.naziv_stanja == k.naziv_stanja ):
                        stanja_za_izbacit.append(k)
                        break

            if ( len (stanja_za_izbacit) > 0 ):     #tu se izbacuju stanja za koja su vec generirani prijelazi
                for k in stanja_za_izbacit:
                    nova_stanja.remove(k)

class Stanje:

    naziv_stanja = ""
    lista = []
    lijeva_strana = []
    prije_tocke = []
    nakon_tocke = []

    def __init__(self, lijeva_s, prije_t, nakon_t, lista):

        self.lista = lista
        self.lijeva_strana = lijeva_s
        self.prije_tocke = prije_t
        self.nakon_tocke = nakon_t
        temp = []

        for i in self.prije_tocke:
            temp.append(i)
            temp.append(' ')
        try:
            temp.pop()
        except:
            temp=[]

        string_liste = ""
        for i in lista:
            string_liste += i + "|"
        tmp_naziv_stanja = self.lijeva_strana + ["->"] + temp + ["*"] + self.nakon_tocke + ["|{" + string_liste + "}"]
        for i in tmp_naziv_stanja:
            self.naziv_stanja += i




import re
class Automat:
    def __init__(self, st, zn, prih, poc, prijelaz):
        self.stanja = st
        self.znakovi = zn
        self.prih_stanja = prih
        self.pocetno_stanje = poc
        self.prijelazi = prijelaz
        self.epsilon = {}
    def epsilon_okruzenje(self,stanja):
        novaStanja = []
        stanje = stanja[0]
        if stanje in self.epsilon.keys():
            novaStanja = self.epsilon[stanje]
            return novaStanja
        while stanja != novaStanja:
            stanja.sort()
            novaStanja = stanja
            for i in stanja:
                if i in self.prijelazi:
                    if '$' in self.prijelazi[i]:
                        for k in self.prijelazi[i]['$']:
                            if k not in stanja:
                                stanja.append(k)
            stanja.sort()
        self.epsilon.update({stanje:novaStanja})
        return novaStanja
    
def pretvori_u_NKA(eNKA,NKA):
        #eNKA.prijelazi = {'q0':{'a':['q1'],'b':['q2'],'c':['q1'],'$':['q1','q3']},'q1':{'a':['q2','q1'],'b':['q1'],'c':['q3'],'$':['q2']},'q2':{'a':['q2'],'b':['q1'],'c':['q3']},'q3':{'a':['q2']}}
        #eNKA.stanja = ['q2','q1','q3','q0']
        #eNKA.pocetno_stanje='q0'
        #eNKA.prih_stanja.append('q2')
        #eNKA.znakovi = ['a','b','c','$']
        NKA.stanja = eNKA.stanja
        NKA.znakovi = eNKA.znakovi
        NKA.prih_stanja = eNKA.prih_stanja
        NKA.pocetno_stanje = eNKA.pocetno_stanje
        for i in eNKA.stanja:
            #print(i)
            eps = eNKA.epsilon_okruzenje([i])
            #print('izasao')
            for j in eNKA.znakovi:
                tmp = []
                got = []
                for t in eps:
                    try:
                        for a in eNKA.prijelazi[t][j]:
                            if a not in tmp:
                                tmp.append(a)
                    except:
                        continue
                for t in tmp:
                    list = eNKA.epsilon_okruzenje([t])
                    for a in list:
                        if a not in got:
                            got.append(a)
                if len(got)>0:
                    if i in NKA.prijelazi.keys():
                        NKA.prijelazi[i].update({j:got})
                    else:
                        NKA.prijelazi.update({i:{j:got}})
        st = [eNKA.pocetno_stanje]
        list = eNKA.epsilon_okruzenje(st)
        list.remove(eNKA.pocetno_stanje)
        for i in list:
            if i in NKA.prih_stanja:
                NKA.prih_stanja.append(eNKA.pocetno_stanje)
                break

        return NKA



def pretvori_u_DKA(NKA,DKA):
    DKA.stanja = [DKA.pocetno_stanje]
    DKA.znakovi = NKA.znakovi
    novi=[]
    for z in NKA.prijelazi[NKA.pocetno_stanje]:
        tmp=''
        tmp2=[]
        for a in NKA.prijelazi[NKA.pocetno_stanje][z]:
            tmp2.append(a)
        tmp2.sort()
        for each in tmp2:
            tmp+=each+','
        tmp = tmp[:len(tmp)-1]

        if tmp not in DKA.stanja + novi:
            novi.append(tmp)

        if DKA.pocetno_stanje in DKA.prijelazi.keys():
            DKA.prijelazi[DKA.pocetno_stanje].update({z:tmp})
        else:
            DKA.prijelazi.update({DKA.pocetno_stanje:{z:tmp}})

    while len(novi) >0:
        #print(len(novi))
        novi_novi=[]
        DKA.stanja+=novi
        for stanje in novi:
            for znak in DKA.znakovi:
                tmp=''
                tmp2=[]
                for jed in re.split(',',stanje):
                    try:
                        for a in NKA.prijelazi[jed][znak]:
                            if a not in tmp2:
                                tmp2.append(a)
                    except:
                        continue
                tmp2.sort()
                for each in tmp2:
                    tmp+=each+','
                if tmp != '':
                    tmp = tmp[:len(tmp)-1]
                    if tmp not in DKA.stanja + novi_novi:
                        novi_novi.append(tmp)
                    if stanje in DKA.prijelazi.keys():
                        DKA.prijelazi[stanje].update({znak:tmp})
                    else:
                        DKA.prijelazi.update({stanje:{znak:tmp}})
        novi=novi_novi
    DKA.prih_stanja = DKA.stanja

    return DKA

class akcija:
    def __init__(self):
        self.ime_akcije=''
        self.stanje=''
        self.produkcija=[]
        self.lijeva_strana=''
        self.desna_strana=[]

def napravi_tablicu(DKA,pocetni):
    tablica = {}

    for stanje in DKA.prijelazi:
        stanja = re.split(',',stanje)
        for znak in DKA.prijelazi[stanje]:
            akc = akcija()
            ime_stanja=stanje+'%'+znak
            akc.stanje=DKA.prijelazi[stanje][znak]
            if znak[0] == '<':
                akc.ime_akcije='Stavi'
            else:
                akc.ime_akcije='Pomakni'
            tablica.update({ime_stanja:akc})
 
    for stanje in DKA.stanja:
        akc=akcija()

        if stanje == pocetni:
            ime_stanja=ime_stanja=stanje+'%'+'#'
            akc.ime_akcije='Prihvati'
            tablica.update({ime_stanja:akc})
            #print(tablica[ime_stanja].ime_akcije)
            continue
        stanja = re.split(',',stanje)
        
        for i in stanja:
            #print(i)
            if i == pocetni:
                ime_stanja=ime_stanja=stanje+'%'+'#'
                akc.ime_akcije='Prihvati'
                tablica.update({ime_stanja:akc})
                continue
            try:
                i=re.split('\*',i)
                #print(stanje)
                if i[1][0]=='|':
                    akc.ime_akcije='Reduciraj'
                    niz=re.split('->',i[0])
                    akc.lijeva_strana = niz[0]
                    #print(niz[1])
                    akc.desna_strana = re.split(' ',niz[1])
                    if akc.desna_strana[0] == '':
                        akc.desna_strana[0] = '$'
                    tmp=re.split('\|',i[1][2:len(i[1])-2])
                    for each in tmp:
                        ime_stanja=stanje+'%'+each
                        if ime_stanja not in tablica.keys():
                            tablica.update({ime_stanja:akc})
            except:
                continue
    
    return tablica


def main():

    a=Generator()
    a.citaj()
    poc2 = a.pocetni
    a.dodaj_pocetni()
    a.izracunaj_prazne()
    a.zapocinje_izravno_znakom()
    a.zapocinje_znakom()
    a.dodaj_tocke()
    lista_stavaka = a.vrati_lr_stavke()
    poc = a.pocetni + '->*' + poc2 + '|{#|}'
    e_NKA_automat = e_NKA(lista_stavaka, a.zavrsni_znakovi, a.nezavrsni_znakovi, a.pocetni, list(a.prazni_znakovi), a.tablica)        #sve je zapisano u listama
    
    t1 = time.time()
    e_NKA_automat.stvori_automat(poc)
    t2 = time.time()
    vrijeme_e_NKA = round(t2 - t1,1)
    
    br = 0
    tmp = e_NKA_automat.sva_stanja
    jednaka = 0
    
    for i in e_NKA_automat.sva_stanja:
        for j in tmp:
            if ( i.naziv_stanja == j.naziv_stanja):
                jednaka +=1
        br += 1
    print("Broj stanja eNKA:  ",br)
    print("jednakih stanja: ", jednaka - br)
    imena = []
    
    for i in e_NKA_automat.sva_stanja:
        imena.append(i.naziv_stanja)
    eNKA = Automat(imena, a.znakovi, imena, poc, e_NKA_automat.prijelazi)
    NKA = Automat([],[],[],'',{})
    #print(eNKA.prijelazi)
    
    t1 = time.time()
    NKA = pretvori_u_NKA(eNKA, NKA)
    t2 = time.time()
    vrijeme_NKA = round(t2 - t1,1)
    

    DKA = Automat([],[],[],'',{})
    tmp=''
    tmp2=eNKA.epsilon_okruzenje([poc])
    tmp2.sort()
    
    for i in tmp2:
        tmp+=i + ','
    tmp=tmp[:len(tmp)]
    DKA.pocetno_stanje = tmp
    
    t1 = time.time()
    DKA = pretvori_u_DKA(NKA,DKA)
    t2 = time.time()
    vrijeme_DKA = round(t2 - t1,1)

    br = 0
    for i in DKA.stanja:
        br += 1
    print("Broj stanja DKA:  ",br)
    #print(DKA.znakovi)
    indeks = poc.find(poc2)
    poc = poc[:indeks-1] + poc2 + '*' + poc[indeks+len(poc2):]
    
    t1 = time.time()
    tab=napravi_tablicu(DKA,poc)
    t2 = time.time()
    vrijeme_DKA_tab = round(t2 - t1,1)
    
    print("Vremena izvodenja (u sekundama):")
    print("e_NKA: ",vrijeme_e_NKA,",  NKA: ",vrijeme_NKA,",   DKA: ",vrijeme_DKA,",   DKA izrada tablice: ",vrijeme_DKA_tab)
    ukupno = vrijeme_e_NKA+vrijeme_NKA+vrijeme_DKA+vrijeme_DKA_tab
    print("Ukupno [min] : ",ukupno/60)
    #for i in tab:
        #print(i)
        #print(tab[i].ime_akcije)
        #print(tab[i].stanje)
        #if tab[i].ime_akcije == 'Reduciraj':
            #print(tab[i].lijeva_strana+'->')
            #print(tab[i].desna_strana)

    file = open('./analizator/tab.pkl','wb')
    pickle.dump(tab,file)
    file.close()

    file = open('./analizator/sink.pkl','wb')
    pickle.dump([a.sinkronizacijski_znakovi,DKA.pocetno_stanje],file)
    file.close()

    file = open('./analizator/zav.pkl','wb')
    pickle.dump(a.zavrsni_znakovi,file)
    file.close()

if __name__ == "__main__": main()







